package solution.s_129;

/**
 * 解题思路：
 *      定义 sum 保存所有子节点所有数字之和，strValue 保存当前节点的字符串数值。
 *      比如从根节点到子节点的路径为 1->2->3，那么在 2 这个节点上，strValue 就是 “12”。
 *      利用递归，遍历整棵树，将子节点的 strValue 转换成数字返回，与 sum 值进行相加，最后
 *      直到整棵树遍历完，sum 即为需要的结果。
 */
public class Solution20201029 {
    public int sumNumbers(TreeNode root) {
        if (root == null) { return 0; }

        String strValue = "";
        return sumNumbers(root, strValue);
    }

    public int sumNumbers(TreeNode node, String strValue) {
        int sum = 0;

        // 当到达子节点的时候，将父节点的 strValue 与 子节点的数字进行拼接，返回相应字符串的数字值。
        if (node.left == null && node.right == null) {
            return Integer.parseInt(strValue + node.val);
        }

        // 当有左子树的时候，sum 的值就是当前值加上左子树的值。
        if (node.left != null) {
            sum += sumNumbers(node.left, strValue + node.val);
        }

        // 当有右子树的时候，sum 的值就是当前值加上右子树的值。
        if (node.right != null) {
            sum += sumNumbers(node.right, strValue + node.val);
        }

        return sum;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
